liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A novel approach to multiple constant multiplication using minimum spanning trees
Linköping University, The Institute of Technology. Linköping University, Department of Electrical Engineering, Electronics System.ORCID iD: 0000-0003-3470-3911
Linköping University, The Institute of Technology. Linköping University, Department of Electrical Engineering, Electronics System.
2002 (English)In: Midwest Symposium on Circuits and Systems,2002, Piscataway, NJ: IEEE , 2002, 652- p.Conference paper, Published paper (Refereed)
Abstract [en]

In this work a novel approach to multiple constant multiplication based on minimum spanning trees is proposed. Each required coefficient is assigned to a vertex in a graph. The vertices are connected with weighted edges, where each edge weight corresponds to the number of adders required to derive one of the coefficient from the previous. The graph can be used to solve for the minimum spanning tree, which leads to a realization with a small number of adders. The optimal minimum spanning tree can be found in polynomial time. It is also possible to add extra constraints to the spanning tree, such as limited out-degree (corresponds to fan-out) and limited tree height (corresponds to delay). These problems are harder to solve, but there are good heuristics available. It is shown by simulation that the performance of the proposed algorithm is comparable with recently published algorithms.

Place, publisher, year, edition, pages
Piscataway, NJ: IEEE , 2002. 652- p.
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-34598Local ID: 22201OAI: oai:DiVA.org:liu-34598DiVA: diva2:255446
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2015-03-11

Open Access in DiVA

No full text

Other links

http://ieeexplore.ieee.org/iel5/8452/26621/01187124.pdf

Authority records BETA

Gustafsson, OscarWanhammar, Lars

Search in DiVA

By author/editor
Gustafsson, OscarWanhammar, Lars
By organisation
The Institute of TechnologyElectronics System
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 239 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf