Abstracts Category : Other

Improved Subset Generation For The MU-Decoder

by Utsav Agarwal

The MU-Decoder is a hardware subset generator that finds use in partial reconfigurationof FPGAs and in numerous other applications. It is capable of generating a set S of subsetsof a large set Z_n with n elements. If the subsets in S satisfy the isomorphic totally-ordered property, then the MU-Decoder works very efficiently to produce a set of u subsets in O(log n) time and (n u log n) gate cost. In contrast, a vain approach requires (un)gate cost. We show that this low cost for the MU-Decoder can be achieved without the isomorphism constraint, thereby allowing S to include a much wider range of subsets. We also show that if additional constraints on the relative sizes of the subsets in S can be placed, then u subsets can be generated with (n u) cost. This uses a new hardware enhancement proposed in this thesis. Finally, we show that by properly selecting S and by using some elements of traditional methods, a set of (un^log( log (n/log n))) subsets can be produced with (n u) cost.Advisors/Committee Members: Busch, Konstantin (Costas) (committee member), Trahan, Jerry (committee member), Vaidyanathan, Ramachandran (chair).