Source: https://patents.google.com/patent/US8862854B2/en
Timestamp: 2019-10-15 15:17:29
Document Index: 149942117

Matched Legal Cases: ['application No. 60', 'art←0', 'art←0', 'art+1', 'art+2', 'art+1']

US8862854B2 - Configurable decoder with applications in FPGAs - Google Patents
US8862854B2
US8862854B2 US12/310,217 US31021707A US8862854B2 US 8862854 B2 US8862854 B2 US 8862854B2 US 31021707 A US31021707 A US 31021707A US 8862854 B2 US8862854 B2 US 8862854B2
US12/310,217
US20100180098A1 (en
2006-08-18 Priority to US83865106P priority Critical
2007-08-20 Application filed by Louisiana State University and Agricultural and Mechanical College filed Critical Louisiana State University and Agricultural and Mechanical College
2007-08-20 Priority to PCT/US2007/018406 priority patent/WO2008021554A2/en
2007-08-20 Priority to US12/310,217 priority patent/US8862854B2/en
2009-07-31 Assigned to NATIONAL SCIENCE FOUNDATION reassignment NATIONAL SCIENCE FOUNDATION CONFIRMATORY LICENSE (SEE DOCUMENT FOR DETAILS). Assignors: LOUISIANA STATE UNIVERSITY A&M COL BATON ROUGE
2010-07-15 Publication of US20100180098A1 publication Critical patent/US20100180098A1/en
2014-10-14 Publication of US8862854B2 publication Critical patent/US8862854B2/en
2016-01-29 Assigned to BOARD OF SUPERVISORS OF LOUISIANA STATE UNIVERSITY AND AGRICULTURAL AND MECHANICAL COLLEGE reassignment BOARD OF SUPERVISORS OF LOUISIANA STATE UNIVERSITY AND AGRICULTURAL AND MECHANICAL COLLEGE ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: VAIDYANATHAN, RAMACHANDRAN
2016-01-29 Assigned to BOARD OF SUPERVISORS OF LOUISIANA STATE UNIVERSITY AND AGRICULTURAL AND MECHANICAL COLLEGE reassignment BOARD OF SUPERVISORS OF LOUISIANA STATE UNIVERSITY AND AGRICULTURAL AND MECHANICAL COLLEGE ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: JORDAN, MATTHEW
2016-06-15 Assigned to NATIONAL SCIENCE FOUNDATION reassignment NATIONAL SCIENCE FOUNDATION CONFIRMATORY LICENSE (SEE DOCUMENT FOR DETAILS). Assignors: LOUISIANA STATE UNIVERSITY, BATON ROUGE
229910007609 Zn—S Inorganic materials 0 description 2
239000011701 zinc Substances 0 description 49
This application claims the priority of U.S. provisional application No. 60/838,651 filed on Aug. 18, 2006, and the contents thereof are hereby incorporated by reference in its entirety.
This invention relates to decoders. Specifically, it relates to mapping units and configurable decoders based upon mapping units, where each device outputs more bits, than are input to it.
A number of applications benefit from a technique called dynamic reconfiguration, in which elements of the FPGA chip are reconfigured to alter their interconnections and functionality while the application is executing on the FPGA. Dynamic reconfiguration has two main benefits. First, a dynamically reconfigurable architecture can reconfigure between various stages of an application to use its resources efficiently at each stage. That is, it reuses hardware resources more efficiently across different parts of an algorithm. For example, an algorithm using two multipliers in Stage 1 and eight adders in Stage 2 can run on dynamically reconfigurable hardware that configures as two multipliers for Stage 1 and as eight adders for Stage 2. Consequently, this algorithm will run on hardware that has two multipliers or eight adders, as opposed to a non-configurable architecture that would need two multipliers and eight adders.
In order to facilitate partial reconfiguration, FPGAs are typically divided into sets of frames, where a frame is the smallest addressable unit for reconfiguration. In current FPGAs, a frame is typically one or more columns of CLBs. Currently, partial reconfiguration can only address and configure a single frame at a time, as a 1-hot decoder is usually employed. If we assume that each CLB receives the same number of configuration bits, say α, and the number of CLBs in each frame is the same, say C, then the number of configuration bits needed for each frame is Cα. If the number of bits needed for selecting a single frame is b, then the total number of bits B needed to reconfigure a frame is:
B=b+Cα.
The O(·) notation indicates an upper bound on the “order of” and is used to describe how the size of the input data affects resources (time, cost etc.) in an algorithm or hardware. Specifically, for two functions f(n) and g(n) of a variable n, we say that f(n)=O(g(n)) if and only if, there is positive constant c>0 and an integer constant n0, such that for all n≧n0, we have f(n)≦cg(n). The relationship f(n)=O(g(n)) signifies that the “order of” (or asymptotic complexity of) f(n) is at most that of g(n) or that f(n) increases at most as fast as g(n). If O( . . . ) denotes a lower bound on the complexity, then Ω(·) and Θ(·) indicates an upper bound on, and the exact complexity, respectively. Specifically, f(n)=Ω(g(n)) if and only if g(n)=O(f(n)). We say f(n)=Θ(g(n)) if and only if f(n)=O(g(n)) and f(n)=Ω(g(n)).
Parts of the invention will be described in terms of “ordered partitions.” A partition of set A is a division of the elements of the set into disjoint non-empty subsets (or blocks). A partition π with k blocks is called a k-partition. For example, a 3-partition of the set {8, 7, 6, 5, 4, 3, 2, 1, 0} is {{7, 6, 5, 4}, {3, 2}, {1, 0}}, Partitions have no imposed order. An ordered k-partition is a k-partition {So, Sl, . . . , Sk−1} with an order (from 0 to k−1) imposed on the blocks. An ordered partition will be denoted
. For instance, a 2-partition {So, S1}, may be ordered as
S0, Sl
A useful operation on partitions is the product of two partitions. Let π1 and π2 be two (unordered) partitions (not necessarily of the same size). Let π1={S0, S1, . . . , Sk} and π2={P0, P1, . . . , Pl}, then their product π1π2 is a partition {Q0, Q1, . . . , Qm} such that for any block Qhεπ1π2, elements a, bεQh if and only if there are blocks Siεπ1 and Pjεπ2, such that a, bεSi∩Pj. That is, two elements are in the same block of π1π2 if and only if they are in one block of π1 and in one block of π2. For instance, consider the partitions π1={{7, 6, 5, 4}, {3, 2}, {1, 0}} and π2={{7, 6}, {5, 4, 3, 2}, {1, 0}}. Then π1π2={{7, 6}, {5, 4}, {3, 2}, {1, 0}}=π2π1.
For any digital circuit, including those considered in this invention, an n-bit output can be viewed as a subset of an n-element set. Let Zn={0, 1, . . . , n−1}. Consider an n-bit signal A=A(n−1)A(n−2) . . . A(0) (where A(i) is the ith bit of A; in general, we will consider bit 0 to be the least significant bit or the lsb). If A is an n-bit output signal (or word) of a digital circuit, then it can be viewed as the subset {iεZn:A(i)=1} of Zn. The n-bit string A is called the characteristic string of the above subset. The set {iεZn:A(i)=1} is said to be characterized by A and is sometimes referred to as the characteristic set. For example if n=8, then output A=00001101 corresponds to the subset {0, 2, 3}. Outputs 00000000 and 11111111 correspond to the empty set, 0/ and Zn, respectively. (It should be noted that the convention could be changed to exchange the meanings of 0's and 1's. That is, a 0 (resp., 1) in the characteristic string represents the inclusion (resp., exclusion) of an element of Zn in the set. All ideas presented in this document apply also to this “active-low” convention.)
Throughout this document, we assume (unless mentioned otherwise) that the base of all logarithms is 2. Consequently, we will write log n to indicate log2 n. We will also use the notation logα n to denote (log n)α.
Storing information within the design attempts to alleviate the pin limitation problem by generating most information needed for execution of an application inside the chip itself (as opposed to importing it from outside the chip). This requires a more “intelligent” chip. In an FPGA setting it boils down to an array of coarse grained processing elements rather than simple functional blocks (CLBs). One example is the use of virtual wires in which each physical wire corresponding to an I/O pin is multiplexed among multiple logical wires. The logical wires are then pipelined at the maximum clocking frequency of the FPGA, in order to utilize the I/O pin as often as possible. Another example of such a solution is the Self-Reconfigurable Gate Array. This latter approach is a significant departure from current FPGA architectures. Yet another approach is to compress the configuration information, thereby reducing the number of bits sent into the chip.
Decoders are the third means used to address the pin limitation problem. A decoder is typically a combinational circuit that takes in as input a relatively small number of bits, say x bits, and outputs a larger number of bits, say n bits, according to some mapping; such a decoder is called an “x-to-n decoder.” If the x inputs are pins to the chip and the n outputs are expanded within the chip, a decoder provides the means to deliver a large number of bits to the interior of the chip. An x-to-n decoder (that has x input bits) can clearly produce no more than 2x output sequences, and some prior knowledge must be incorporated in the decoder to produce a useful expansion to n output bits. Decoders have also been used before with FPGAs in the context of configuration compression, where dictionary based or statistical schemes are employed to compress the stream of configuration bits. Our invention when used in the context of FPGAs has more application in selecting parts of the chip in a more focused way than conventional decoders do. However in a broader context, the method we propose is a general decoder for any scheme employing fixed size code words, that decode into (larger) fixed size target words.
As we noted earlier, for any digital circuit, including a decoder, an n-bit output can be viewed as a subset of the n-element set Zn={0, 1, . . . , n−1}. Thus, the set of outputs produced by an x-to-n decoder can be represented as a set of (at most 2x) subsets of Zn.
TABLE 1 Example of 3-to-8 Decoders Decoder Inputs S0 S1 S2 S3 000 00000001 01010101 11111111 00001101 001 00000010 10101010 00001111 10010010 010 00000100 00110011 00000011 10100010 011 00001000 11001100 00000001 00111101 100 00010000 00001111 11110000 01001110 101 00100000 11110000 11000000 11010001 110 01000000 11111111 10000000 11100001 111 10000000 00000000 00111100 01111110
Sets S0, S1, S2 and S3 represent different decoders, each producing subsets of Zn. For instance, S0 corresponds to the set of subsets {{0}, {1}, {2}, . . . {7}}. This represents the 3-to-8 one-hot decoder.
Current decoders in FPGAs are fixed decoders, producing a fixed set of subsets (output bit combinations) over all possible inputs. The fixed decoder that is normally employed in most applications is the one-hot decoder that accepts a (log2 n)-bit input and generates a 1-element subset of Zn, (see set S0 in Table 1). (In subsequent discussion all logarithms will be assumed to be to base 2, that is, log n=log2 n.) In fact, the term “decoder” is usually taken to mean the one-hot decoder.
Look-up tables (LUTs) can function as a “configurable decoder.” A 2x×n LUT is simply a (2x)-entry table, where each entry has n bits. It can produce 2x independently chosen n-bit patterns that can be selected by an x-bit address. LUTs are highly flexible as the n-bit patterns chosen for the LUT need no relationship to each other. Unfortunately, this “LUT decoder” is also costly; the gate cost of such a LUT is O(n2x). For a gate cost of O(n log n), a LUT decoder can only produce O(log n) subsets or mappings. To produce the same number of subsets as a one-hot decoder, the LUT decoder has O(n2) gate cost. Clearly, this does not scale well.
It is an object of the invention to allow the multicasting of x bits into n bits, a bits at a time, through hardwired circuitry, where the hardwired route is selected by an input selection word from a reconfigurable memory device.
It is an object of the invention to provide a reconfigurable mapping unit in conjunction with a second reconfigurable memory unit, where the second memory unit allows for selection of the z bits to be input into the reconfigurable mapping unit from x bits, where x<z.
Accordingly, the invention includes a reconfigurable mapping unit that is a circuit, possibly in combination with a reconfigurable memory device. The circuit has as input an x-bit word having a value at each bit position, and a selector bit word, input to the circuit. The circuit outputs an n-bit word, where n>x, where the value of each bit position of the n-bit output word is based upon the value of a pre-selected hardwired one of the bit positions in the x-bit word, where said hardwired pre-selected bit positions is selected by the value of the selector bit word. The invention may include a second reconfigurable memory device that outputs the z-bit word, based upon an input x-bit word to the second memory device, where x<z. The invention may produce the output n bit, a bits at a time.
FIG. 3 shows a block diagram for the function of a fan-in of degree f and width w.
FIG. 4 shows a block diagram for the function of a fan-out of degree f and width w.
FIG. 8 shows an implementation of a 2x×m LUT.
SR ⁡ ( z , z α ) .
SR ⁡ ( z , z α )
FIG. 11 shows a block diagram of a mapping unit MU(z, y, n, α).
FIG. 13 shows the general structure of a mapping unit MU(z, y, n, α).
FIG. 14 shows a fixed mapping unit MU(4, 1, 8, 1) that produces the set of subsets S0 and S1 of Table 2.
FIG. 15 shows a fixed mapping unit MU(4, 2, 8, 1) that produces all three sets of subsets of Table 2.
FIG. 17 shows an implementation of a bit-slice mapping unit MU(z, y, n, α).
FIG. 18 shows the structure of a mapping-unit-based configurable decoder MUB(x, z, y, n, α).
FIG. 22 shows the hardwired partitions used in the two parallel MU-B decoders in an optimal configuration generating the 1-hot subset of Zn.
FIG. 23 shows a parallel O(n)-cost one-hot 4-to-16 fixed decoder; here n=16.
FIG. 24 shows a general structure of a parallel MU-B decoder MUB(x, z, y, n, α, P).
Here a decoder is a combinational circuit (with the exception of the bit-slice units later described), that, in order to achieve a greater degree of flexibility, can be combined with look-up tables (LUTs), to create a configurable mapping unit or a configurable decoder. While LUTs could be implemented using sequential elements, for this work, LUTs are functionally equivalent to combinational memory such as ROMs. Any type of memory could be used for a LUT.
Recall that any x-to-n decoder (including the mapping unit) takes x bits as input and outputs n bits, and the set of subsets generated by the configurable mapping unit decoder are those tailored in part for the application at hand. Different applications require different sets of subsets of Zn, and do so with different constraints on speed and cost. The reconfigurable mapping unit and configurable decoder have a portion of the hardware that can be configured (off-line) to modify the output bit pattern. This allows one to freely select a portion of the subsets produced by the mapping unit or reconfigurable decoder. Hence, given an understanding of the problem to be addressed, the mapping unit and/or configurable decoder may be configured to address the specific problem.
Recall that an x-to-n decoder produces a set S of subsets of Zn. We denote the number of elements in S by Λ, that denotes the total number of subsets produced by the decoder. Clearly, Λ≦2x. The decoder allows some of the Λ subsets to be chosen arbitrarily (the independent subsets) while other subsets are set by prior choices (the dependent subsets). Let S⊂S′ denote the portion of subsets that can be produced independently by the decoder. For instance, in a LUT decoder, all entries are independent, while in a fixed decoder (non-configurable) there are no independent subsets. We define the following two parameters that are specific to decoders.
Number of independent subsets=λ=number of elements in S
A fan-in operation combines f signals into a single output, while a fan-out takes a single input signal and generates f output signals. The fan-in and fan-out operations are as follows:
For integers f, z>1, let U0, U1, . . . , Uf−1 be f signals, each z bits wide. A fan-in operation of degree f and width z produces a z-bit output W whose ith bit W(i)=U0(i)∘U1(i)∘ . . . ∘ Uf−1(i). The operator o is an associative Boolean operation, such as AND, OR, NOR, etc. Diagrammatically, FIG. 3 shows a fan-in operation.
For integers f, z>1, let U be a z-bit wide signal. A fan-out circuit of degree f and width z produces f outputs W0, W1, . . . , Wf−1, each z bits wide, where Wj(i)=U(i). Diagrammatically, FIG. 4 shows a fan-out operation.
Fan-in and fan-out circuits of degree f and width z can be constructed with a gate cost of O(fz) and a delay of O(log f).
Fixed Decoders-One-Hot Decoders:
A x-to-n decoder is a (usually combinational) circuit that takes x bits of input and produces n bits of output, where x<n. Usually x
n, and a decoder is used to expand an input from a small (2x-element domain to an output from a large (2n)-element set.
In general, an x-to-2x one-hot decoder has a delay of O(x) and a gate cost of O(x2x).
A 2x-to-1 multiplexer can be implemented as a circuit with a gate cost of O(x2x) and a delay of O(x).
A 2x×m LUT can be implemented as a circuit with a gate cost of O(2x(x+m)) and a delay of O(x+log m).
Define an α-position shift register of width z/α, denoted by
SR ⁡ ( z , z α ) ,
as follows. It accepts as input a z-bit signal, and every clock cycle, outputs a
( z α ) ⁢ - ⁢ bit
slice of that signal. FIG. 9 diagrams the operation. The shift register can also be configured as a parallel-to-serial converter. That is accept z/α, bits during each cycle, and output an n-bit word every α cycles. FIG. 10 is a circuit implementation of such a shift register.
An α-position shift register of width z/α,
can be realized as a circuit with a gate cost of O(z) and a constant delay between clock cycles.
Modulo-α Counter: For any α>1, a modulo-α (or mod-α) counter increments its output by ‘1’ every clock cycle, returning to ‘0’ after a count of α−1. Modulo-α counters are well known in the art.
A modulo-α counter can be realized as a circuit with gate cost O(log2 α) and a delay of O(log log α).
The base unit of the invention is the mapping unit, and its features are diagrammed in FIG. 11. The mapping unit MU(z, y, n, α) can be viewed as a type of decoder: it takes in a small number of bits (z bits) and expands them to a larger number of bits (n bits), where typically z<<n. We will refer to the z-bit input as the source word, the y-bit input as the selector address (or the selector address word), and the n-bit output as the output word.
The mapping unit accomplishes the expansion of the z-bit source word to the n-bit output word by “multicasting” the z-bits to n places. A multicast of z bits to n bits (or z places to n places) is a one-to-many mapping from the z source bits to the n output bits, such that each output bit is mapped onto from exactly 1 source bit, but each source bit may map to 0, 1 or more output bits. The multicast operation typically transfers the value of a source bit to the output bit it is mapped to. Here we will use it in a more general sense in that the output bit derives its value from the source bit it is mapped from, for example by complementation. Unless we note otherwise, a multicast transfers the value of each source bit to its corresponding output bits. (The inclusion of parameters y and α in the mapping unit MU(z, y, n, α) will be described later).
As an illustration, consider a multicast of four bits a(3), a(2), a(1), a(0) to 8 bits b(7), b(6), b(5), b(4), b(3), b(2), b(1), b(0), such that b(0)=a(0), b(1)=6(3)=b(5)=b(7)=a(3), b(2)=b(6)=a(2) and b(4)=a(1). If a=0111, then b=01010101 (FIG. 12( a)). If a=0011, then b=00010001 (FIG. 12( b)). A different 4 to 8 mapping of a to b will result in different outputs. For example, if the mapping is b(0)=a(0), b(1)=a(1), b(2)=b(3)=a(2) and b(4)=b(5)=b(6)=b(7)=a(3), then for a=0111, b=00001111 (FIG. 12( c)), while if a=0011, then b=00000011 (FIG. 12( d)). The mapping unit of the invention is broader than a unit containing one fixed multicasting operation. It uses several fixed multicasts, and the choice of the multicast operation to be employed is selected by the value of the y-bit selector address input to the mapping unit, as shown in FIG. 11. Hence, the number of possible multicasts used in a MU(z, y, n, α) is 2y.
Another characterization of a multicast is in terms of an ordered partition. Consider a multicast of bits a(z−1), a(n−2), . . . , a(1), a(0) to bits b(n−1), b(n−2), . . . , b(1), b(0). An ordered z-partition
S0, S1, . . . , Sz−1
of Zn={0, 1, . . . , n−1} represents this multicast if and only for all bit positions j of a particular block Si, b(j) gets its value from a(i).
For example, the multicasts of FIGS. 12( a),(b) and (c),(d) correspond to the ordered 4-partitions {right arrow over (π)}1=
and {right arrow over (π)}2=
{7, 6, 5, 4}, {1}, {0}
. The ordered partition represents the mapping of the source word bits to the output word bits, where the position of the block in the partition (for instance block {7, 5, 3, 2} is in position 4 of {right arrow over (π)}1) represents the position of the source word bit (position 4 here), and the value of the block ({7, 5, 3, 2} here) represents the output word bit positions to which the value of the input bit get mapped or cast into (here a(4) gets mapped to b(7), b(5), b(3) and b(2)). Hence a mapping unit can be considered a mapping of a z-bit source word to an n-bit output word, using an ordered partition selected by the selector address (y bits), or a mapping
μ:Z 2 z ×Z 2 y →Z 2 n .
In summary, MU(z, y, n, α) accepts as input a z-bit source word, U, and an ordered partition {right arrow over (π)} (one among 2y) as selected by the y-bit selector address, B, of FIG. 11, and produces as output an n-bit output word (or a subset of Zn). The source word could assume any value from {0, 1}z. The set of 2y ordered partitions is fixed (usually hardwired in the mapping unit) and/or configured into a LUT internal to the mapping unit.
As described, a mapping unit is a decoder that accepts as input a z-bit source word u and an ordered z-partition {right arrow over (π)} of an n-element set (specified in terms of a y-bit selector address). It produces an n-bit output word. Mapping units can be classified as integral or bit-slice. An integral mapping unit generates all n output bits simultaneously and (for reasons explained below) has the parameter α set to 1. A bit-slice mapping unit, on the other hand, generates the n output bits in a rounds; i.e., n/α bits at a time. One could view the integral mapping unit as a bit-slice mapping unit with α=1. Another way to categorize mapping units (both integral and bit-slice) is in terms of whether they are fixed or configurable (that is, based on whether they can be configured off-line to alter their behavior). Configurable mapping units can be general or universal. In informal terms, a universal mapping unit can produce any subset. Fixed mapping units cannot be universal (unless n is very small or a very high cost can be accepted).
A general structure of a mapping unit, MU(z, y, n, α), is as shown in FIG. 13. The n-bit output word comes from a bank of n multiplexers (MUXs). MUX i (where 0≦i<n) accepts 2yi data bits as input and uses yi control bits. Each data input of a MUX is hardwired from one of the z source bits. This relationship between the source word and MUX inputs is fixed at the time of manufacture (even for configurable mapping units); although, in principle, some amount of configurability may be introduced in these connections. Denote the yi-bit control signal of MUX i by Bi. The concatenated control bits
is called the selector word of the mapping unit. The selector word can be of different sizes and can be generated in a variety of ways in different types of mapping units. The mapping unit has, embedded in its structure, room for 2y different selector words, each corresponding to an ordered partition (or a multicast scheme from the source word to the output word). These selector words are generated and chosen by the selector module, using a y-bit selector address. The different selector words can be stored in a “configuration LUT” and/or expressed by the value of the selector address. For the mapping unit models we discuss beyond this point, yi=y. This need not be the case, however, in general. The control bits can be derived in any manner from the y selector address bits, for example, by directly hardwiring a subset of the y bits to each MUX control. At the other extreme is using a LUT for the selection module with wordsize w such that
max ⁢ { y i ⁢ : ⁢ ⁢ 0 ≤ i < n } ≤ w ≤ ∑ i = 0 n - 1 ⁢ y i .
Here, some or all of the w bits in each selector word can be used to control a MUX.
In the fixed mapping unit (FMU), the y-bit selector address is broadcast as the control signal to each MUX. That is, the selector module constructs the selector word by concatenating n copies of the selector address. Therefore, yi=y. As an example, let z=4, y=1, and n=8. Then there are 2y=2 ordered partitions mapping the 4 source word bits to the 8 output word bits. Let the mappings be as shown in FIGS. 12( a),(b) and (c),(d), which produce the sets of subsets S0 and S1 from Table 2. The resulting FMU is shown in
TABLE 2 Example sets of subsets of Z8. Sj i S0 S1 S2 S0 i 11111111 11111111 10100010 S1 i 01010101 00001111 11111101 S2 i 00010001 00000011 01011010 S3 i 00000001 00000001 00000111
FIG. 14. Notice that if input signal B=0, then U(0) is connected to Q(0), U(1) is connected to Q(4), U(2) is connected to Q(2) and Q(6), etc. This matches the configuration shown in FIGS. 12( a) and (b). Similarly, if B=1, then U(0) is connected to Q(0), U(1) is connected to Q(1) etc. It can be shown that a fixed mapping unit can be realized as a circuit with a gate costs of O(ny2y) and a delay of O(y+log n).
It can be shown that a configurable mapping unit, MU(z, y, n, α), can be realized as a circuit having a gate cost of O(ny2y) and a delay of O(y+log n).
As an example of the functionality of a configurable mapping unit, consider the fixed mapping unit with z=2y of FIG. 15 which implements all four sets of subsets in Table 2. If a CMU was used to implement the same set of subsets using the same wiring of the signal U to the n-multiplexers, then Table 3 shows the contents of the configuration LUT. Note that the contents specify an ordered partition corresponding to a set of subsets, and not the subset
TABLE 3 Configuration LUT words to produce the subsets of Table 2. selector address ny-bit selector word Set b ∈ B in LUT Si 00 00 00 00 00 00 00 00 00 S0 01 01 01 01 01 01 01 01 01 S1 10 10 10 10 10 10 10 10 10 S2 11 11 11 11 11 11 11 11 11 S3
itself. For example, when b=00, the LUT word is 00 00 00 00 00 00 00 00 corresponding to the ordered partition {right arrow over (π)}0 for set S0 (see Tables 2 and 4). Then with u=0111, we have the output word μ(u, {right arrow over (π)}0)=01010101. Similarly, with u=0011, we μ(u, {right arrow over (π)})=00010001. Thus, in this illustration, the selector address b=00 corresponds only to the ordered partition {right arrow over (π)} for S0.
There are two important properties of the configurable mapping unit. The first is that from a perspective outside of the mapping unit, nothing changes between a fixed mapping unit and a configurable mapping unit; that is, to produce a desired subset Sj i, the same values are needed for signals U and B in a configurable mapping unit as they are in a fixed mapping unit. The second is that each “grouping” of the y control bits (each corresponding to a particular MUX) in the ny-bit selector words has the same value in an FMU; If this value is v, then each of the n output bits is derived from the ordered partition {right arrow over (π)}v. However, this does not have to be the case in a CMU. For example, a word in the LUT illustrated in Table 3 could have the value 00 01 10 11 00 01 10 11; this is a combination of values of different ordered partitions for different MUXs. For example, bits 7, 6 and 5 of the 8-bit output word would be derived from {right arrow over (π)}0, {right arrow over (π)}1 and {right arrow over (π)}2, respectively, as 00, 01 and 10 are the binary representations of 0, 1 and 2, respectively. This would result in multicast with the ordered partition
{7, 6, 3, 1}, {4, 2}, {0}, {5}
As we described earlier, an ordered partition is an abstract representation of a multicast from the source word to the output word. It is possible for different source words to use the same ordered partition to generate different output words (or subsets). Ideally, the 2z source words and 2y (ordered partition) selector words should produce 2z+y distinct output words, each of which must be one of interest to us. This requires a careful selection of ordered partitions and source words.
Here we describe a procedure (called Procedure Part_Gbn) that creates partitions (multicasts) for a mapping unit MU (z, y, n, α). As a vehicle for explanation, we will also impose an (arbitrary) order on the partitions we generate. Later we will present a method to order the partition systematically. Procedure Part_Gen generates one of many possible sets of partitions. Subsequently, another procedure will outline how one could use Procedure Part_Gen to find a suitable set of partitions.
Let S be a set of subsets of Zn that we wish the mapping unit to generate. A given subset S of Zn (i.e., a particular n-bit output word having bit positions indexed 0 to n−1) induces a 1- or 2-partition πS, where πS is the 1-partition {Zn} if S is empty or S=Zn; otherwise, πS is the 2-partition {S, Zn−S}. The induced partition is not unique for a given S as πS=πZ n −S={Zn−S, S}. When a subset is represented by an n-bit sequence (as described earlier), the induced partition creates two blocks, one containing the bit positions that have a 0 value, and the other block containing the bit positions having a 1 value. For instance, if the subset is represented by the bit stream 10001100, then the induced partition is the 2-partition {{0, 1, 4, 5, 6}, {2, 3, 7}}, while if the input bit stream is 11111111, then the induced partition is the 1-partition {{0, 1, 2, 3, 4, 5, 6, 7}}. The induced partition is not an ordered partition.
Let S={S0, S1, . . . , Sk−1} be a set of subsets of Zn, and let each subset Si induce the partition πS i . Define the partition induced by S to be the product of the individual induced partitions, πS=πS 0 πS 1 . . . πS k−1 . An example will illustrate these ideas. Consider the set of subsets of S0, S1 and S2 (of Z8) in Table 2, where each set of subsets has Tour elements, i.e. Si={S0 i, S1 i, S2 i, S3 i}, for 0≦i≦2. The partitions induced by each element of the set of subsets is contained in Table 4 (note, there are four induced partitions for each Si, corresponding to its four elements). Then,
TABLE 4 Partitions πS j i for subsets Sj i of Table 2. Sj i πS j 0 πS j 1 πS j 2 S0 i {{7, 6, 5, 4, 3, 2, 1, 0}} {{7, 6, 5, 4, 3, 2, 1, 0}} {{6, 4, 3, 2, 0}, {7, 5, 1}} S1 i {{7, 5, 3, 1}, {6, 4, 2, 0}} {{7, 6, 5, 4}, {3, 2, 1, 0}} {{1}, {7, 6, 5, 4, 3, 2, 0}} S2 i {{7, 6, 5, 3, 2, 1}, {4, 0}} {{7, 6, 5, 4, 3, 2}, {1, 0}} {{7, 5, 2, 0}, {6, 4, 3, 1}} S3 i {{7, 6, 5, 4, 3, 2, 1}, {0}} {{7, 6, 5, 4, 3, 2, 1}{0}} {{7, 6, 5, 4, 3}, {2, 1, 0}}
Procedure Part_Gen({right arrow over (S)}, z); generates partitions for {right arrow over (S)}, each with ≦z blocks.
1. For each SiεS, compute its induced partition πS i .
3: Starting from πl, pick the largest integer m such that πS l πS l+1 . . . πS l+m−1 has ≦z blocks. Let π1=πS l πS l+1 . . . πS l+m−1 .
4. Repeat this process until all induced partitions πS i have been included in some πj.
The partitions π0, π1, . . . are the outputs of Procedure Part_Gen. The basic idea of the procedure is to “add” subsets in the prescribed order into the current partition until the partition has too many blocks. Then it starts afresh with the next partition. We will use this notion of “adding a subset” to an existing partition later in this discussion. We illustrate the procedure with the following example.
Let S=S0∪S1∪S2 using the sets in Table 2, let z=4, then
{right arrow over (S)}={S 0 0 ,S 1 0 ,S 2 0 ,S 3 0 ,S 1 1 ,S 2 1 ,S 0 2 ,S 1 2 ,S 2 2 ,S 3 2}.
πS 0 ,0·πS 1 0 ·πS 2 0 ={{7,5,3,1},{6,2},{4,0}}
πS 1 1 ·πS 2 1 ={{7,6,5,4},{3,2},{1,0}}=π1
πS 0 2 ·πS 1 2 ={{7,5},{1},{6,4,3,2,0}}
πS 0 2 ·πS 1 2 ·πS 2 2 ·πS 3 2 ={{7,5},{2,0},{6,4,3},{1}}=π2
{right arrow over (π)}0={{7,5,3,1},{6,2},{4},{0}},
{right arrow over (π)}1={{7,6,5,4},{3,2},{1,0}},
{right arrow over (π)}2={{7,5},{2,0},{6,4,3},{1}}.
A subset not in S can also be produced. For example, using the z-bit source word 1010 with the ordered partition {right arrow over (π)}0 produces the output word 10111010 that corresponds to the subset {7, 5, 4, 3, 1} which is not in S.
In the procedure, a different sequence of considering the induced partitions πS j i can produce a different set or number of ordered partitions. For example, if the induced partitions were considered in reverse order, that is, starting with πS 3 2 , such that the non-ordered partitions were π0=πS 3 2 πS 2 2 πS 1 2 etc., then the resulting ordered partitions would be {right arrow over (π)}0=
{7, 5}, {2, 0}, {6, 4, 3}, {1}
, {right arrow over (π)}1=
, and {right arrow over (π)}2=
{7, 5, 3, 1}, {6, 2}, {4, 0}
for S1 results in the same set of 4 source words for both sets of subsets. We describe a similar effect for binary reductions (discussed later).
It can be shown that, if the partitions of the mapping unit MU(z, y, n, α) are not fixed, then the mapping unit can generate a number of independent subsets λ≧2y └log z┘, provided 2y log z≦2x. If the partitions are fixed and z+y≦n, then it can be proved that the number of independent subsets is 0.
It can be shown that for integers n, z≧2, and
y ≤ ⌈ n z - 1 ⌉ )
there exists a mapping unit that uses C values from {0, 1, . . . , 2z−1} as source words and Y≦2ξ ordered partitions to produce CY distinct subsets. That is, it is possible to construct a mapping unit with z+y bits of input (where
ξ = ⌈ n z - 1 ⌉ ,
that produces 2y(2z−2) distinct outputs (which is not too far from the theoretically maximum possible number of 2y+z=2y2z distinct outputs).
Suppose a partition places output word indices i and j in the same block. Suppose the hardwired connections are such that no bit of the
TABLE 5 Two different orderings for the partitions of sets S0 and S1 resulting in different sets of source words used to produce the subsets in each set. Sj i π z-bit value needed Q S0 0
1111 11111111 S1 0 0111 01010101 S2 0 0011 00010001 S3 0 0001 00000001 S0 0
1111 11111111 S1 0 1101 01010101 S2 0 1001 00010001 S3 0 0001 00000001 S0 1
1111 11111111 S1 1 0111 00001111 S2 1 0011 00000011 S3 1 0001 00000001 S0 1
{3, 2}, {0}, {7, 6, 5, 4}, {1}
1111 11111111 S1 1 1101 00001111 S2 1 0101 00000011 S3 1 0100 00000001
source word connects to both MUXs i and j. In this case, we cannot select a source word bit to multicast to output word bits i and j. That is, the given partition cannot be realized on the existing hardwired connections.
For each output word bit position 0≦j<n, let Gj denote the set of source word bits that have been hardwired to one of the data inputs of the MUX at position j. For example in the mapping unit of FIG. 15, the multiplexers at output position 4 is connected to source word positions 1, 2 and 3. Similarly output position 5 (resp., 6) is connected to source word positions 0 and 3 (resp., 2 and 3). Thus G4={1, 2, 3}, G5={0, 3} and G6={2, 3}. For any subset B of Zn (representing output positions), define the set HB to be the set of source word indices that are connected to MUXs at every one of the output positions in B. That is,
H B = ⋂ j ∈ B ⁢ G j .
A partition π is said to be realizable on a set of hardwired connections between the source word and MUX inputs if and only if there exists for each output position j, an assignment of a source word position ij, such that for any two output bit positions 0≦j, j′<n in (not necessarily distinct) blocks. B and B′ of π,
(b) If B=B′, then ij=ij′; call this common source word position iB.
The intuition is that the hardwired connections support a multicast from source word bit ij to output position j. Since ij is unique to the block containing j, the multicast is restricted to be within a block. In fact, the indices ij convert π into the ordered partition if.
Clearly, a given partition may not be realizable on a set of hardwired connections. Is it possible to check if a given partition IT is realizable, and if so, order it accordingly?
Given π, construct a bipartite graph Gπ=(Zz∪π, E); that is, the set of nodes includes the bit positions of the source word and the blocks of π. For any iεZz and Bεπ, there is an edge between i and B if and only if iεHB.
Let the given partition π have k blocks. We now show that the π is realizable if and only if g has a matching with k edges. Suppose Gπ, has a matching with k edges. Clearly, this matching cannot include an edge that is incident on more than one block. Therefore the matching has exactly one edge per block. Each edge in a matching matches a block B to a unique source word bit position in the source set, HB, of B. This implies that it is realizable and in fact, the matching gives an order that must be imposed on π. Conversely, if π is realizable, then it must have a unique source word index iBεZz, for each block B, such that iBεHB. Since iBεHB, we have an edge between iB and B in graph Gπ. Consequently, the unique correspondence to each block B from a source word position iB constitutes a matching with k edges. Finally observe that if a k-element matching exists, then it must be a maximum matching as no matching can have more edges than there are blocks in the partition; this is because at most one edge in a matching can be incident on each node representing a block.
Let B be a block of a partition π. Clearly as B increases in size; HB tends to decreases in size. In fact, it is possible for HB to be empty, in which case the partition is clearly not realizable. If hardwired connections were random, a good strategy would be to construct, partitions whose blocks have roughly the same size. This could be a guiding principle for the algorithm. If the hardwired connections follow some pattern, then that information could be used to develop a heuristic to select partitions with small blocks.
In general, determining an order that results in a realizable z-partition is not easy. In fact it is possible for the partition as induced by a single subset S to be unrealizable.
The third phase is needed for those subsets SiεS for which πS i itself is not realizable. The third phase splits these subsets Si further with the aim of generating the elements of Si a few at a time. This is similar to the approach followed by bit-slice mapping units (described later). In the extreme case if Si is generated one element at a time, the strategy uses the same method currently followed in one-hot decoders.
Consider now a set of 2y partition πk (where 0≦k<2y), each of which is realizable on a set of hardwired connections. By the definition of realizability, we have ordered πk into an ordered partition {right arrow over (π)}k. Let ij k be the source word position associated with output j in some block Bε{right arrow over (π)}k. This implies that source word bit ij kεGj; that is, source word bit ij k is connected to some input (say input γj k) of the MUX corresponding to output j.
wk,0, wk,1, . . . , wk,n−
, where for any 0≦j<n, we have 0≦wk,j<y. Configure the LUT so that wk,j=γj k. This will ensure that whenever line k of the LUT (or partition {right arrow over (π)}k) is addressed, it will activate input γj k of the MUX (or bit ij k of the source word) as required.
For 0≦l<2y and 0≦j<n, let ml,j represent input l of multiplexer j. The aim is to assign each of these multiplexer inputs to one of the z source word bits s0, s1, . . . , sz−1.
Map input ml,j to bit sq, where q=(l+2yj)(mod z). We called this mapping “overlapped mapping.” For example, if y=2, z=5 and is =16, then the sequence of source word bit indices is as follows:
( 0123 1234 2340 3401 4012 0123 1234 2340 ⁢ ⁢ 3401 4012 0123 1234 2340 3401 4012 0123 ︷ source ⁢ ⁢ word ⁢ ⁢ bits ) ( 0 ⁢ 1 ⁢ 2 ⁢ 3 ⁢ 4 ⁢ 5 ⁢ 6 ⁢ ⁢ 7 ⁢ 8 ⁢ 9 ⁢ 10 ⁢ 11 ⁢ 12 ⁢ 13 ⁢ 14 ⁢ 15 ︸ output ⁢ ⁢ bit )
With overlapped mapping, a set of q consecutive multiplexers have 2y−(q−1) common source word bits. If Q is a block of an unordered partition, then any of these common source word bits form HQ and can be used to assign the order of the block as indicated earlier.
As an example with n=16 and z=5, consider the partition π={B0, B1, B2, B3, B4}={{0, 1, 2, 3}, {4}, {5, 6, 7}, {8, 9, 10, 11}, {12, 13, 14, 15}}. Here HB 0 ={3}, HB 1 ={0, 1, 2, 4}, HB 2 ={2, 3}, HB 3 ={1} and HB 4 ={0}. Assigning source word bits s3, s4, s2, s1, s0 to blocks B0, B1, B2, B3, B4 achieves the desired order. In general, this approach works well when subsets include proximate indices. However, the method is not guaranteed to work under all situations.
In the earlier example of the section entitled “Hardwiring a mapping unit:” suppose that π′={B0′, B1′, B2′, B3′, B4′} where B0′={0, 1, 2, 3}, B1′={4}, B2′={5, 6, 7}, B3′={10, 11, 12, 13} and B4′={8, 9, 14, 15}. The corresponding sets HB i ′ are {3}, {0, 1, 2, 4}, {2, 3}, {3}, and {0, 1}, respectively. Clearly, we cannot assign a unique source word bit to each block as HB 0 ′=HB 3 ′={3}; that is, both B0′ and B3′ have 3 as the only possible source word bit to connect to. If we use the partition π described earlier and permute the outputs so that Bi maps to Bi′, for each 0≦i≦4, we get the desired output as shown in FIG. 16.
This post permutation can be achieved by a butterfly network whose switches are configurable 2-input multiplexers. This network has a O(n log n) gate cost and O(log n) delay; that would not significantly alter the cost of the mapping unit in most cases. Also the network can be configured as needed using standard permutation-routing algorithms for the butterfly network. It may also be possible to use a butterfly network with fewer than the standard 1+log n stages as permutations among proximate outputs may not be required. This would further reduce the cost of the butterfly network.
Although this method does not guarantee that the hardwiring would allow every partition to be realizable, many practical problems that exhibit regularity and structure tend to be more amenable to analytical approaches and individualized fine-tuning.
A fixed mapping unit MU(z, y, n, α) fans-out the y-bit selector address to all n MUXs (shown as signals B0, B1, . . . , Bn−1; here B0=B1= . . . =Bn−1. In contrast, these ny bits of MUX control come from the configuration LUT in a configurable mapping unit; here y selector address bits are used to address at most 2y LUT locations, each ny bits long. In this case the signals B0, B1, . . . , Bn−1 are completely independent of each other. We now describe two hybrid schemes.
As before, let Zn represent the set of MUXs in the mapping unit. For some integer 1≦l<n, partition Zn into E blocks; Let this partition be {R0, R1, . . . , Rl−1}. (This partition has nothing to do with the partition of the outputs associated with the multicast from the source word bits.) Use a configuration LUT with wordsize ly. If a configuration word has the form
then each MUX with index iεRj receives control input {circumflex over (b)}{circumflex over (bj)}. As before, this reduces the size of the configuration LUT.
The advantage of both hybrids is that they reduce the size of the LUT word to ly<ny. This reduces the cost of the LUT if its size is kept the same. Alternatively, this can also allow one to increase the number of words in the LUT for the same cost as in the configurable mapping unit. An implication of this is that the configuration LUT can now store more partitions (say 2y′/partitions for some y′>y) for the same cost as the configurable mapping unit. This would require y′ bits to be input to the configuration LUT. However, only y of these bits would be used with F and each MUX (regardless of whether it is in F or R) would still use y control bits and, consequently, we would still hardwire only 2y source word bits to each MUX. This is needed to keep the collective cost of the n MUXs the same as before.
The hybrid mapping units can be viewed as a generalizations of the fixed and configurable mapping units. For the first hybrid, when F=Zn (or R=0/), we have the fixed mapping unit and when R=Zn (or F=0/) we have the configurable mapping unit. The second hybrid is a generalization of the configurable mapping unit; if l=n, then we have the standard configurable mapping unit. When l=1, then all MUXs received the same control signal as in the fixed mapping unit, but if a LUT of wordsize y is used, then the y control bits of the MUXs need not be the same as the y (or y′) bits input to the mapping unit.
4.1.9 Universal Mapping Unit
A mapping unit MU(z, y, n, α) is universal if and only if it can, under configuration, produce any set of 2y log z independent subsets of Zn. It can be shown that a configurable mapping unit with z=2y is universal. This is because, when z≦2y, each bit of the source word can be input to every MUX. Consequently, any partition B has HB={0, 1, . . . , z−1}. Thus a universal mapping unit MU(2y, y, n, α) with O(ny2y) gate cost and O(y+log n) delay exists.
A bit-slice mapping unit generates just part of the output subset (represented by an n-bit word) at a time. It constructs a subset over α iterations, generating n/α bits in each iteration. This allows the mapping unit to exploit repeated patterns, such as these demonstrated in Table 6, representing two forms of reduction. Notice that to generate 8 words, each 16 bits long, only 6 words, each 4 bits long, need to be generated. For example, the subset S corresponding to word
TABLE 6 Subsets with repeated patterns for n = 16 and α = 4. Subset S Repeated Patterns 1111111111111111 1111 0001000100010001 0001 0000000100000001 0000, 0001 0000000000000001 0000, 0001 0000000011111111 0000, 1111 0000000000001111 0000, 1111 0000000000000011 0000, 0011 0000000000000001 0000, 0001
0001000100010001 can be constructed over 4 iterations using the bit pattern 0001. Overall, this allows the bit-slice mapping unit to decrease the required gate cost of its internal components in situations where an increased delay is tolerable.
A possible implementation of MU(z, y, n, α) is shown in FIG. 17. A shift register (SR) acts as a parallel to serial converter and stores the z-bit source words and outputs n/α bits every α cycles to the internal mapping unit
( n α ⁢ - ⁢ bit )
words into one n-bit word. A mod-α counter orchestrates this parallel to serial conversion by triggering a write-in operation on the input shift register and a write-out on the output shift register every a cycles. This allows a new source word to be input into the bit-slice mapping unit and an n-bit output q written out every a cycles.
Because the bit-slice mapping unit is a sequential circuit, we modify the definition of delay. For sequential circuits, we assume that the clock delay of the circuit to be the longer of (a) the longest path between any flip-flop output and any flip-flop input and (b) the longest path between any circuit input and output. Using this notion of delay, it can be shown that a bit-slice mapping unit MU(z, y, n, α) can be realized in a circuit with a gate costs of
λ = 2 y α ⁢ ⌊ log ⁢ ⁢ z α ⌋
and a delay of O(α(log log α+log n+y)), and the number of independent subsets is
O ( log 2 ⁢ α + n ⁡ ( 1 + y ⁢ ⁢ 2 y α ) )
and the maximum total number of subsets producible is Λ=2y/(2z−2), provide
y < ⌈ n z - 1 ⌉ .
A point that that needs attention is the matter of how partitions play out in the bit-slice mapping unit. For example, the subsets of Table 6 produced by a fixed mapping unit MU(z, y, n, α) with z=5, 2y=2 require two ordered partitions
{15,14,13,11,10,9,7,6,5,3,2,1},{12,4,}{8},{0}
⌈ z α ⌉ = 2 ,
n α = 4 ,
two ordered partitions {right arrow over (π)}1′=
{3, 2}, {1, 0}
and {right arrow over (π)}2′=
{3, 2, 1}, {0}
( a ) ⁢ ⁢ delay ⁢ ⁢ of ⁢ ⁢ O ⁡ ( a ⁡ ( y + log ⁢ ⁢ n ) ) , ⁢ ( b ) ⁢ ⁢ gate ⁢ ⁢ cost ⁢ ⁢ of ⁢ ⁢ O ⁡ ( n ⁡ ( 1 + y ⁢ ⁢ 2 y α ) ) , ⁢ ( c ) ⁢ ⁢ number ⁢ ⁢ of ⁢ ⁢ independent ⁢ ⁢ subsets ⁢ ⁢ producible = λ = 2 y α ⁢ ⌊ log ⁢ ⁢ z α ⌋ , ⁢ and ⁢ ( d ) ⁢ ⁢ maximum ⁢ ⁢ number ⁢ ⁢ of ⁢ ⁢ subsets ⁢ ⁢ producible = Λ = 2 y ⁢ ( 2 z - 2 ) , ⁢ provided ⁢ ⁢ y < ⌈ n z - 1 ⌉ .
A 2x×n look-up table or LUT may be considered as a type of x-to-n configurable decoder. A 2x×n LUT also takes in an x-bit input word and outputs up to 2x words, each n bit wide, where the n-bit words are determined by the contents of the LUT's memory array. Unfortunately, this “LUT decoder” is expensive, where the gate cost of is O(2x(x+n)). If this decoder was implemented on the same scale as a log n-to-n one-hot decoder, then x=log n. This results in a decoder that, while able to produce (after configuration) any of the 2n subsets of Zn, has a gate cost of Θ(n2). On the other hand, if the LUT decoder were restricted to the same asymptotic gate cost as the one-hot decoder (that is, Θ(n log n)), it would only be able to produce Θ(log n) subsets of Zn (being at most a log n×n LUT). Although the flexibility of the LUT decoder is desirable, its cost does not scale well and an alternative is needed.
By incorporating a “narrow” output LUT with a mapping unit that expands this narrow output into a wide n-bit output representing a subset of Zn, a device is obtained that is reduced in cost (compared to a LUT decoder) but has substantial flexibility. FIG. 18 shows a block diagram of the mapping-unit-based decoder. To put the figure in perspective, x
z<<n, generally. Unlike the LUT decoder solution, this solution expands the x-bit input in stages to construct the n-bit output.
As FIG. 18 shows, the x-to-n MU-B decoder (denoted by MUB(x, z, y, n, α)) has two main components, a 2x×z LUT and a mapping unit MU(z, y, n, α). The LUT maps an x-bit input to a narrow z-bit word. The mapping unit MU(z, y, n, α) accepts this z-bit LUT output as an input source word u. It also accepts an ordered partition if as indirectly selected by the y-bit selector word B). The MU(z, y, n, α) then uses the operation μ(u, {right arrow over (π)}) to produce an n-bit word representative of a subset of Zn. Any MU(z, y, n, α) in combination with a 2x×z LUT (or other type of memory) is considered a type of MU-B decoder, MUB(x, z, y, n, α) as shown in FIG. 18.
The next example illustrates a MU-B decoder with a bit-slice mapping unit. Consider the sets S0={S0 0, S1 0, S2 0, S3 0} and S1={S0 1, S1 1, S2 1, S3 1} shown in Table 7. Let S=S0∪S1 and let
TABLE 7 Set S = S0 ∪ S1. Sj i q ∈ Q z ∈ U S0 0 1111111111111111 11111 S1 0 0101010101010101 01111 S2 0 0001000100010001 00111 S3 0 0000000100000001 00011 S4 0 0000000000000001 00001 S0 1 1111111111111111 11111 S1 1 0000000011111111 01111 S2 1 0000000000001111 00111 S3 1 0000000000000011 00011 S4 1 0000000000000001 00001
z=5 and 2y=2. It is easy to verify that the ordered partitions for sets S0, S1 are
{5,14,13,12,11,10,9,8},{7,6,5,4},{3,2},{1},{0}
respectively. Then MUB(x, z, y, n, α) fixed mapping unit would require 16 multiplexers with 2 inputs each and a 5×5 LUT to hold the values of the source words (note that this is due to an intelligent ordering; in general the LUT could be as large as a 10×5).
⌈ z α ⌉ = 2
n α = 4 ⁢ ⁢ bit
For these n/α-bit words, three partitions are needed,
This would imply a reduction in cost by a factor of
TABLE 8 Source and output words for S. Sj i ⌈ z α ⌉ - bit ⁢ ⁢ ⁢ input ⁢ ⁢ word n α - bit ⁢ ⁢ word ⁢ ⁢ produced S0 0 11 1111 S1 0 01 0101 S2 0 01 0001 S3 0 00, 01 0000, 0001 S4 0 00, 01 0000, 0001 S0 1 11 1111 S1 1 00, 11 0000, 1111 S2 1 00, 11 0000, 1111 S3 1 00, 01 0000, 0011 S4 1 00, 01 0000, 0001
⌈ z α ⌉ ) .
Thus, the implementation depends on the allowable costs, the number of z-bit source words and the corresponding size of the LUT, and the subsets that must be produced. Further, the ordering of the partitions can determine not only the size of the LUT in the MU-B decoder (and thus also the values of its parameters), but also dictate the subsets that can be produced.
It can be shown that: for any α≧1, a mapping-unit-based configurable decoder MUB(x, z, y, n, α) has a delay of O(x+log z+α(y+log n)) and a gate cost of
O ⁡ ( 2 x ⁢ ( x + z ) + n ⁡ ( 1 + y ⁢ ⁢ 2 y α ) ) ;
further, MUB(x, z, y, n, α) can produce at least
λ = min ⁢ { 2 x , 2 y α ⁢ ⌊ log ⁢ ⁢ z α ⌋ }
y ≤ ⌈ n z - 1 ⌉ - 1 ) ,
Let P be a LUT decoder, and let C be the proposed mapping-unit-based configurable decoder, each producing subsets of Zn. If both decoders have a gate cost G, such that G=Ω(n) and G is polynomially bounded in n, then for constant σ>0,
⊖ ( n ε ⁢ log σ ⁢ n log ⁢ ⁢ log ⁢ ⁢ n )
⊖ ( log ⁢ ⁢ n log ⁢ ⁢ log ⁢ ⁢ n )
more dependent subsets, where 0ε<1.
Θ ⁡ ( G n ⁢ ( n ε log σ ⁢ n ) )
In discussing binary reduction, we consider a more general case involving a set S of totally ordered subsets. Let S={S0, S1, . . . , Sk−1} be a set of k subsets of Zn such that S0⊃S1⊃ . . . ⊃Sk−1; that is, the elements of S are totally ordered by the “proper superset of relation. For each 0≦i<k, let πS i denote the partition induced by Si. It can be shown that
π = ⁢ π S 0 · π S 1 ⁢ ⁢ … ⁢ ⁢ π S k - 1 = ⁢ { { S 0 , S 1 - S 0 , S 2 - S 1 , … ⁢ , S k - 1 - S k - 2 , Z n - S k - 1 } , if ⁢ ⁢ S k - 1 = Z n { S 0 , S 1 - S 0 , S 2 - S 1 , … ⁢ , S k - 1 - S k - 2 } , if ⁢ ⁢ S k - 1 ⋐ Z n
For binary reduction, k=1+log n=log 2n in the above notation and Slog n=Zn. Therefore,
π={S 0 ,S 1 −S 0 ,S 2 −S 1 , . . . ,S log n −S log n−1}
The first reduction pattern has subsets S0 0={0}, S1 0={0, 4}, S2 0={0, 2, 4, 6} and S3 0={0, 1, 2, 3, 4, 5, 6, 7}. This results in the partition π0={{7, 5, 3, 1}, {6, 2}, {4}, {0}}. Similarly, the second reduction pattern produces the partition π1={{7, 6, 5, 4}, {3, 2}, {1}, {0}}.
TABLE 9 Two binary tree based reduction patterns S0 i n-bit pattern S1 i n-bit pattern S0 0 00000001 S1 0 00000001 S0 1 00010001 S1 1 00000011 S0 2 01010101 S1 2 00001111 S0 3 11111111 S1 3 11111111
A binary reduction corresponding to a partition π={S0, S1−S0, S2−S1, . . . , Slog n−Slog n−1} can be implemented on MUB(log log 2n, log 2n, 1, n, α). A MUB(log log 2n, log 2n, y, n, α) can implement 2y/different binary reductions. Since corresponding subsets in different binary reductions still have the same number of elements, the same set of log 2n source words can be used for all reductions; different ordered partitions need to be used, however.
The reduction corresponding to the unordered partition π0={{7, 5, 3, 1}, {6, 2}, {4}, {0}} can be ordered so that the blocks (in the order shown) correspond to source words bits 3, 2, 1, 0 (where 0 is the least significant bit or lsb). Thus, the output set (represented as an n-bit word with bit 0 as the lsb) produced by source word s3, s2, s1, s0 and the ordered partition is s3, s2, s3, s1, s3, s2, s3, s0. To produce the sets S0 0, S1 0, S2 0, S3 0 the source words are 0001, 0011, 0111, 1111, respectively. If we now order π1={{7, 6, 5, 4}, {3, 2}, {1}, {0}} so that the blocks (in the order shown) correspond to source word bits 3,2,1,0, then it is easy to verify that the same source words 0001, 0011, 0111, 1111 produce sets S0 1, S1 1, S2 1, S3 1, respectively.
A set of one-hot subsets is a set of subsets of Zn, each represented by an n-bit output word with each output word having only one active bit (usually with a value of ‘1’), all other bits being inactive (usually ‘0’). (The ideas we present also apply to decoders using an active-low logic where a ‘0’ represents inclusion of an element of Zn in the subset and ‘1’ represents exclusion of the element from the subset.) Table 10 shows an example for active-high logic.
The structure of the partition induced by a set of one-hot subsets is a particular case of a set of disjoint subsets, that we now describe. Let S={S0, S1, . . . , Sk−1} be a set of subsets of Zn, that are pairwise disjoint; that is, for any 0>i,j<k, S1∩Sj=∅. Let
TABLE 10 A set of 1-hot subsets of Z16 Si n-bit value S0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 S1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 S2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 S3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 S4 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 S5 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 S6 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 S7 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 S8 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 S9 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 S10 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 S11 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 S12 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 S13 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 S14 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 S15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sk=Zn−(S0∪S1∪ . . . ∪Sk−1). It can be shown that the partition induced by the sets in S is
π = { { S 0 , S 1 , … ⁢ , S k - 1 } , if ⁢ ⁢ S k = 0 / { S 0 , S 1 , … ⁢ , S k - 1 , S k } , if ⁢ ⁢ S k ≠ 0 /
Thus if the given set S has k disjoint subsets, then the partition induced by S has at most k+1 blocks. For the one-hot set of subsets, k=n and the induced partition is {{0}, {1}, . . . , {n−1}}. Moreover, because the subsets are disjoint, the product of any k partitions πS i induced by a set of k one-hot subsets results in a partition with at least k blocks. Thus if we were to construct z-block partitions, we will need
y = Θ ⁡ ( log ⁢ n z ) = Θ ⁡ ( log ⁢ ⁢ n ) ,
as z is of substantially smaller order than n. This would make the gate cost of the MU-B decoder
Thus, the 1-hot sets are easy to produce in a conventional fixed decoder, they present a difficult embodiment for the MU-B decoder described so far. One method of producing the 1-hot subsets in a MU-B decoder is to use a LUT with 2x=n rows (or x=log n). A LUT contains a 1-hot address decoder, and since a configurable decoder MUB(log n, z, y, n, α) contains a n×z LUT, a simple switch allowing the output of the LUT's address decoder to be the output of the configurable decoder automatically allows the configurable decoder to produce the 1-hot subset. Also, the parallel decoder described subsequently teaches a simple way to construct a one-hot decoder out of MU-B decoders.
For the next discussion, we recognize that ASCEND/DESCEND subsets are in complementary pairs that induce the same partition. In fact each level of the ASCEND/DESCEND algorithm has one complementary pair; that is, there one induced partition per level of the algorithm. For the moment, we consider just a set of log n ASCEND/DESCEND sets (one per level). It is easy to show that the product any k partitions induced by k of ASCEND/DESCEND sets has 2k blocks, each of size
For example, the partition for the first level of communications is π1={{7, 5, 3, 1}, {6, 4, 2, 0}}. Taken for log z such levels, this results in a single z-partition that with 2 log z source words can produce 2 log z of the different 2 log n subsets. For example, consider z=4. Then, log z=2, which implies that two levels can be represented by a single partition. If a partition represents levels one and two, then this results in the partition π={7, 3}, {6, 2}, {5, 1}, {4, 0}).
TABLE 11 Partitions and source words generated for ASCEND/DESCEND subsets for n = 8 and z = 4 Si π Source words output word S0
{7, 3}, {6, 2}, {5, 1}, {4, 0}
1010 10101010 S1 0101 01010101 S2 1100 11001100 S3 0011 00110011 S4
dd10 11110000 S5 dd01 00001111 d denotes a don't care value
Decoders can be structured in a parallel configuration utilizing a merge operation (such as an associative Boolean operation) to combine the outputs of two or more decoders. A parallel embodiment using MU-B decoders will be denoted MUB(x, z, y, n, α, P) where the parameter P denotes the number of configurable decoders connected in parallel. Although we present examples in which a parallel configurable decoder uses multiple instances of configurable decoders of the same size and type, they could, in principle, be all different.
Consider two subsets S0, S1 of Zn. Assume that an integer m divides n, or n=km for some integer k. Then Zn={0, 1, . . . , m−1, m, m+1, . . . , 2m−1, 2m, . . . , im−1, . . . , (i+1)m−1, . . . , (k−1)m, . . . , km−1}. For 0≦i<m and
TABLE 12 Subsets qi,0 and qi,1 for n = 20 and m = 4 n-bit word qi,0 q0,0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 q1,0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 q2,0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 q3,0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 qj,1 q0,1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 q1,1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 q2,1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 q3,1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 q4,1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Let S0={qi,0: 0≦i<m} and
Subsets S0 and S1 induce partitions π0={qi,0: 0≦i<m} and
π 1 = { q j , 1 ⁢ : ⁢ 0 ≤ j < n m } ,
S 1 = { q j , 1 ⁢ : ⁢ 0 ≤ j < n m } .
two z-partitions of n can generate these subsets. Put differently, each subset of S0 and S1 can be independently generated by different MU-B decoders, each using just one partition. Note that qi,0∩qj,1={jm+i}, and it can be shown that for each xεZn, there exists unique values 0≦i<m and
z = k = n m ,
such that xεqi,0∩qj,1, and hence
?? = { q i , 0 ⋂ q j , 1 : 0 ≤ i < m ⁢ ⁢ and ⁢ ⁢ 0 ≤ j < n m }
is the set of one-hot subsets. A simple method to generate the one-hot subsets using parallel decoders is shown in FIG. 21.
If m=√{square root over (n)}, then both m and n/m form feasible values for the input for a mapping unit; that is,
and z0=m=√{square root over (n)}=n/m=z1, and y0=y1=0; also n0=n1=n. Both MU-B decoders use a single partition, hardwired into their respective mapping units, as shown in FIGS. 22( a) and (b).
The cost of each MU-B decoder is the cost of a √{square root over (n)}×√{square root over (n)}LUT with a
MUB ⁡ ( 1 2 ⁢ log ⁢ ⁢ n , n , 0 , n , 0 , 1 )
which is Θ(n). Clearly, increasing y0 and y1 to any constant will increase the number of subsets produced without altering the Θ(n) gate cost.
Two smaller log √{square root over (n)}-to-√{square root over (n)} 1-hot decoders arranged as shown in this example will also produce a larger log n to n 1-hot decoder with O(n) cost (this is elaborated upon further below). However, the MU-B decoder approach offers room for additional partitions and hence additional subsets (within the same asymptotic cost) and considerably higher flexibility.
If the application calls for just a fixed one-hot decoder, a MU-B decoder could be much too expensive. Here the ideas presented for a parallel MU-B decoder are adapted to a fixed one-hot decoder. Let D0 and D1 be two instances of a
q k 0 = p l 0 , where ⁢ ⁢ l = ⌊ k n ⌋ q k 1 = p m 1 ⁢ ⁢ where ⁢ ⁢ m = k ⁢ ⁢ mod ⁢ ⁢ n
one-hot decoder (see FIG. 23 for an example with n=4). Assume that
1 2 ⁢ log ⁢ ⁢ n
is an integer. For i=0,1, let the outputs of Di be pj i, where 0≦j<√{square root over (n)}. That is, if the input to Di (expressed as a binary number) is j, then pj i=1 (or active); otherwise, pj i=0 (or inactive). Fan each of these sets of outputs to n-bit positions qj i as follows. For 0≦j<√{square root over (n)} and 0≦k<n,
1 2 ⁢ log ⁢ ⁢ n ⁢ - ⁢ to ⁢ - ⁢ n
These outputs are the same as those illustrated in Table 12. Therefore, the log n-to-n one-hot decoder outputs rk (where 0≦k<n can be obtained as
r k =q k 0 AND q k 1.
FIG. 23 illustrates this. Since a conventional log n-to-n one-hot decoder has O(log n) delay and O(n log n) gate cost, decoders Di each has O(log n) delay and O(√{square root over (n)} log n) gate cost. Each of the 2√{square root over (n)} fan-outs is of degree √{square root over (n)}, so this has O(log n) delay and O(√{square root over (n)}√{square root over (n)})=O(n) gate cost. The last step of ANDing the two set of n bits clear las constant delay and O(n) gate cost. (Note if an active-low convention is adopted for the decoder, the above AND gates would be replaced by OR gates.)
Overall, this implementation of a one-hot decoder has O(log n) delay and O(n) gate cost. Compared to the conventional implementation of a one-hot decoder exemplified in FIG. 5, our design has comparable delay, but a lower order of cost. In fact, since n outputs are required, this asymptotic gate cost cannot be improved upon.
In general, a P-element parallel configurable decoder MUB(x, z, y, n, α, P) is shown in FIG. 24. As shown, P decoders “receive” all x+y input bits. In use, each decoder CDi, where 0≦i<P, selects a portion xi and yi of the input bit streams x and y, respectively, as the input and selection information.
Two decoders, say MUBi and MUBj may use the same input bit(s) or share some common input bit(s) for their LUTs. Therefore, xi≦x and
∑ i = 0 P - 1 ⁢ y i ≥ y .
as each input bit is assumed to be used at least once. Similarly, yi≦y and
∑ i = 0 P - 1 ⁢ x i ≥ x ,
The merge unit could perform functions ranging from set operations (where ni=n, for all i) to simply rearranging bits (when
∑ i = 0 P - 1 ⁢ n i = n ) .
The (optional) control allows the merge unit to select from a range of options.
Clearly, each MUBi can produce its own independent set of ni-bit outputs. The manner in which these outputs combine depends on the merge unit. For example, let each MUBi produce an n-bit output (that is, a subset of Zn) and let Si be the independent set of subsets produced by MUBi. Let the merge operations be ∘, an associative set operation with identity So. Intersection, Union, and Ex-OR represent such an operation with Zn, 0/, and 0/, respectively, as identities. If each MUBi produces a set of subsets Si that includes So, then the whole parallel MU-B decoder produces an independent set that includes
∑ i = 0 P - 1 ⁢ S i .
Let MUBi have a delay of Di and a gate cost of Gi. If DM and GM are the delay and gate cost of the merge unit, then the delay D and gate cost G of the parallel MU-B decoder MUB(x, Z, y, n, α, P) are
D = max ⁡ ( D i ) + D M + O ⁡ ( log ⁢ ⁢ P ) . ⁢ G = ( ∑ i = 0 P - 1 ⁢ G i ) + G M + O ⁡ ( P ⁡ ( x + y ) ) .
If the merge unit uses simple associative set operations (such as Union, Intersection, Ex-OR) that correspond to bit-wise logical operations, then DM=O(log P) and GM=O(nP). Since x+y≦n, the overall cost and delay for this structure is
D = max ⁡ ( D i ) + O ⁡ ( log ⁢ ⁢ P ) . ⁢ G = ( ∑ i = 0 P - 1 ⁢ G i ) + nP .
1. An apparatus comprising a circuit having a decoder in combination with a mapping unit, where the circuit has as input an x-bit input word having a binary value at each x-bit position, where the x-bit input word is input into the decoder which has a z-bit source word output having binary value at each z-bit position, where the z-bit source word is input into the mapping unit which also receives y-bit selector address input from outside the circuit, where the circuit outputs an n-bit output word having a binary value at each n-bit position, where each n-bit position is hardwire connectable to a subset of said z-bit positions (the “Mapping Subsets”) of the z-bit source word, and where n>z>x.
2. The apparatus of claim 1 where the binary value of each bit position of said n-bit output word is set as the binary value, or the complemented binary value, of a selected one of said z-bit positions in its Mapping Subset (the “Selected Map Bit”).
3. The apparatus of claim 2 where, for a first non-null subset of said n-bit output words bit positions, said Selected Map Bits are chosen by a value of the selector address.
4. The apparatus of claim 3 where said first non-null subset of said n-bit output words bit positions includes all n-bit positions.
5. The apparatus of claim 1 wherein said decoder comprises a look up table (LUT).
6. The apparatus of claim 5, wherein a gate cost of the LUT is substantially lower than a gate cost of a n×n LUT.
7. The apparatus of claim 5 wherein said LUT comprises a LUT of 2x entries, each z bits long.
8. The apparatus according to claim 1 wherein said circuit further comprises n multiplexers, one for each bit position of said n-bit output word, and said z-bit positions are hardwire connectable to said n-bit positions through said multiplexers, as specified in said Mapping Subsets.
9. A method of hardwiring a configurable decoder of claim 8, where each of n multiplexers has a series of input ports ml,j (“ml,j” represents the lth input port of multiplexer j, where l=0, . . . , 2y−1 and j=0, . . . n−1), and where said method comprising the step of wiring each input bit position p to multiplexers input ports ml,j, where p=(i+2yj)(mod z) for all j and n.
10. A mapping-unit-based configurable decoder (a “MU-B Configurable Decoder”) comprising the apparatus of claim 1 where the y-bit selector address is input into a memory device of the mapping unit, which memory device outputs a selector word determined by the selector address.
11. A parallel MU-B configurable decoder comprising a plurality of MU-B configurable decoders {Pk} according to claim 10,
each said Pk MU-B configurable decoder (“Pk”) has a zk-bit source word output from said Pk's associated said decoder, where said Pk's associated decoder has an xk-bit input word, where Pk's associated mapping unit has a yk-bit selector address input to said Pk's associated said memory device of said Pk's associated mapping unit, where said Pk's associated memory device of said Pk's associated mapping unit outputs a Pk selector word, and each Pk outputs a nk-bit output word, where said parallel MU-B configurable decoder combines said set of output words {nk} into an n-bit output word.
12. The parallel MU-B configurable decoder of claim 11 where yk=y, zk=z, and nk=n.
13. The parallel MU-B configurable decoder of claim 11 where said Pk input word is the same word for all k, and said Pk selector word is the same word for all k.
14. The parallel MU-B configurable decoder according to claim 11 wherein a subset of said set of output words {nk} are combined into an n-bit output word using Boolean functions.
15. A parallel MU-B configurable decoder according to claim 11, having a first and a second MU-B decoders, each outputting an output word n1 and n2 of n bits, having x1 and x2 as input words, x1 being log m bits long and x2 being log n/m bits long, where
m = n k ,
for some integer k, and source words z1 and z2, respectively, where z1 is m-bits long and z2 is n/m a bits long, where said selector word is of length y≧l, where each said output word has a characteristic set, where {CN1} is the set of characteristic sets of said output words {N2}, and where {CN2} is the set of characteristic sets of output words, where {CN1} has a subset {qi,1: 0≦i<m}, where and qi,1={i+ml: 0≦l<k} and where {CN2} has a subset
( log ⁢ ⁢ n m ) - bit
where and qj,2={jm+l: 0≦l<M}.
16. An integrated circuit having x′ input pins, and internal portions of said integrated circuit being addressable by n-bit words, where n>x′, said integrated chip incorporating at least one MU-B configurable decoder according to claim 10 having an n-bit output word, wherein said n-bit output word specifies an addressable location internal to said integrated chip.
17. A universal configurable mapping unit decoder comprising the configurable decoder of claim 1 wherein said Mapping Subsets are all n-bit positions of said output word for each input z-bit position.
18. A method of checking if a given k-block partition π is realizable on a set of said hardwired connections of a mapping unit according to claim 1, and if the said partition π is realizable, to order it accordingly, comprising the steps of:
(a) generating the bipartite graph of the said hardwired connections and the said partition π, whose nodes are said z-bit source word positions and the k blocks of said partition π
(b) Find a maximum matching on the graph, if one exists
(c) if the said maximum matching exists and its size is k, then order the said partition π by assigning to each block its matching source node position.
19. A method of constructing a set of realizable ordered partitions on a set of said hardwired connections of a mapping unit according to claim 1, given a desired set of output words {Ai}, comprising the steps of:
(a) applying a method of constructing an ordered partition to create a set of desired output n bit output words {Ak−1, . . . , A0} from a set of desired input z-bit source words (Ij−1, . . . , I0) comprising the steps of:
(i) ordering said set of words {Ak};
(ii) for each said output word element Ak, form its induced partition πAk and assign variables p start←0, and s start←0;
(iii) save the partition πp start=πAs startπAs start+1πAs start+2 . . . πA1 where I is the largest integer such that πp start has less than or equal to z blocks;
(iv) Set variables p start←p start+1 and s start←l+1; and
(v) If said induced partition of an output word Ak has not been considered in step (iii), then go to step (iii);
using different orders of the said set of output words {Ai} in step (i), saving realizable output partitions, ordering the said realizable partitions, and removing from {Ai} all output words encompassed by the said realizable partitions;
(b) iteratively applying step (a) with the allowed partition size decreasing from z−1 down to 2;
(c) breaking each remaining said output words into smaller sets, until their induced partitions are realizable, saving the said realizable partitions, and ordering said realizable partitions.
20. A decoder comprising a circuit, where said circuit has as input an x-bit input word having a binary value at each x-bit position and as-input a selector address, where the x-bit input word is first decoded to a z-bit source word, and where said circuit outputs an n-bit output word, where n>z>x, where said circuit has a selectable fixed number of hardwired multicasts of said z-bit positions to said n-bit positions, where said selector address generates a selector word that selects one of said multicasts, thereby assigning to each n-bit position, the value, or the complemented value, of the z-bit position multicasted to said n-bit position; and where the selector address is a y-bit input.
21. A decoder according to claim 20 wherein the selector word is an output of a memory device which receives the y-bit selector address.
22. A parallel decoder comprising a plurality {Mk} of decoders according to claim 21, where each said Mk decoder has an xk-bit input word and a yk-bit selector address, and where each Mk's associated xk-bit input word is first decoded to a zk-bit source word, and each Mk decoder outputs an nk-bit output word,
where said parallel decoder combines said set of output words into an n-bit output word.
23. A binary reduction decoder (“BR decoder”) comprising a decoder according to claim 21, where y≧1, z=log(2n), x=log log(2n), where said set of possible n-bit output words is {Ak} for a preset configuration of said MU-B decoder, each said n-bit output word having a characteristic set CAk, and said set of characteristic sets {CAk} having at least one subset {Sk}, for k=0 to log n, such that Slog n⊂Slog(n)−1⊂ . . . ⊂S1⊂S0.
24. An apparatus comprising a mapping unit and a decoder, where said mapping unit has as input a z-bit source word, having a binary value at each z-bit position, and as input a selector address, and said decoder has as output the z-bit source word, where said mapping unit outputs an n-bit output word where n>z, where said mapping unit has a selectable fixed number of hardwire multicasts of said z-bit positions to said n-bit positions, where said input selector address selects a selector word from a memory device of the mapping unit, and a value of said selector word chooses, for a fixed subset of said n-bit output word bit positions, one of said multicasts, thereby assigning to each n-bit position in said fixed subset the value, or the complemented value, of the z-bit position multicast to said n-bit position.
25. A configurable decoder comprising a mapping unit in combination with a first memory device, where the mapping unit has as input a z-bit source word from said first memory device having a binary value at each z-bit position, and a selector address input which generates a selector word, and said mapping unit outputs an n-bit word, where n>z, where each n-bit position is hardwire connectable to an associated fixed subset of z-bit positions, where a value of said selector word selects, for a non-empty subset {αi} of said n-bit positions, a corresponding position in said z-bit source word for each αi from that αi's associated fixed subset of z-bit positions,
and said mapping unit assigns, to each αi of the n-bit output word, the binary value (or the complementary value) of the corresponding z-bit position.
26. A configurable decoder according to claim 25 wherein said selector address is input into a second memory device which outputs said selector word.
US12/310,217 2006-08-18 2007-08-20 Configurable decoder with applications in FPGAs Active 2031-02-28 US8862854B2 (en)
US83865106P true 2006-08-18 2006-08-18
PCT/US2007/018406 WO2008021554A2 (en) 2006-08-18 2007-08-20 A configurable decoder with applications in fpgas
US12/310,217 US8862854B2 (en) 2006-08-18 2007-08-20 Configurable decoder with applications in FPGAs
US20100180098A1 US20100180098A1 (en) 2010-07-15
US8862854B2 true US8862854B2 (en) 2014-10-14
US12/310,217 Active 2031-02-28 US8862854B2 (en) 2006-08-18 2007-08-20 Configurable decoder with applications in FPGAs
US14/478,856 Active US9257988B2 (en) 2006-08-18 2014-09-05 Configurable decoder with applications in FPGAs
WO (1) WO2008021554A2 (en)
US9184766B1 (en) * 2014-12-24 2015-11-10 SK Hynix Inc. Decoding circuit
CN105245319B (en) * 2015-08-25 2018-06-29 福州瑞芯微电子股份有限公司 Species stream selection method and system for low power consumption
US20050281116A1 (en) 2002-03-28 2005-12-22 Furber Stephen B Digital memory
2007-08-20 WO PCT/US2007/018406 patent/WO2008021554A2/en active Application Filing
2007-08-20 US US12/310,217 patent/US8862854B2/en active Active
2014-09-05 US US14/478,856 patent/US9257988B2/en active Active
US20150002191A1 (en) 2015-01-01
WO2008021554A3 (en) 2008-05-02
WO2008021554A2 (en) 2008-02-21
US9257988B2 (en) 2016-02-09
US20100180098A1 (en) 2010-07-15
Gaubatz et al. 2004 Public key cryptography in sensor networks—revisited
US7116251B1 (en) 2006-10-03 Programmable serializing data path
Free format text: CONFIRMATORY LICENSE;ASSIGNOR:LOUISIANA STATE UNIVERSITY A&M COL BATON ROUGE;REEL/FRAME:023036/0751
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:JORDAN, MATTHEW;REEL/FRAME:037622/0828
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:VAIDYANATHAN, RAMACHANDRAN;REEL/FRAME:037622/0700
Free format text: CONFIRMATORY LICENSE;ASSIGNOR:LOUISIANA STATE UNIVERSITY, BATON ROUGE;REEL/FRAME:039017/0815